package algorithm.t202110;

import java.util.LinkedList;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/19 8:50
 * @description : 3道
 *  莫等闲，白了少年头，空悲切。
 *  persevere to last 2021.10.19 李红磊
 */
public class t20211019 {

    //542. 01矩阵
    public int[][] updateMatrix(int[][] mat) {
        if (mat == null) {
            return null;
        }

        LinkedList<int[]> queue = new LinkedList<>();
        //将所有的0元素的下标放入队列，将1置为-1
        int rows = mat.length;
        int column = mat[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < column; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    mat[i][j] = -1;
                }

            }
        }

        //设定方向数组
        int[] dirX = {-1, 1, 0, 0};//x的方向数组
        int[] dirY = {0, 0, -1, 1};//y的方向数组

        while (!queue.isEmpty()) {
            int[] index = queue.poll();
            int x = index[0];
            int y = index[1];

            //开始对这个节点进行上下左右四个方向遍历
            for (int i = 0; i < 4; i++) {
                int newX = x + dirX[i];
                int newY = y + dirY[i];

                if (newX < 0 || newX > rows - 1 || newY < 0 || newY > column - 1 || mat[newX][newY] != -1) {
                    continue;
                }

                mat[newX][newY] = mat[x][y] + 1;
                queue.offer(new int[]{newX, newY});

            }


        }

        return mat;
    }

    //994.腐烂的橘子
    public int orangesRotting(int[][] grid) {
        if (grid == null) {
            return -1;
        }

        LinkedList<int[]> queue = new LinkedList<>();
        int rows = grid.length;
        int columns = grid[0].length;
        int number = 0;

        //拿到所有腐烂的橘子
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {

                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    number++;
                }

            }
        }
        if (number != 0 && queue.isEmpty()) {
            return -1;
        }

        if (number == 0) {
            return 0;//说明一个新鲜的橘子都没有，则不需要泛滥，
        }


        int[] dirX = {-1, 1, 0, 0};
        int[] dirY = {0, 0, -1, 1};
        int minute = 0;
        while (!queue.isEmpty()) {
            minute++;
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] index = queue.poll();
                int x = index[0];
                int y = index[1];
                //对四个方向尝试泛滥
                for (int k = 0; k < 4; k++) {
                    int newX = x + dirX[k];
                    int newY = y + dirY[k];

                    if (newX < 0 || newX > rows - 1 || newY < 0 || newY > columns - 1 || grid[newX][newY] != 1) {
                        continue;
                    }
                    grid[newX][newY] = 2;
                    queue.offer(new int[]{newX, newY});

                }

            }


        }

        //所有泛滥结束后，查看是否存在的所有新鲜橘子都泛滥了
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }

        return minute - 1;
    }

    //面试题04.05 合法二叉搜索树
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        } else if (root.left == null && root.right == null) {
            return true;
        }

        return isLegalBinarySearch(root, null, null);


    }

    private boolean isLegalBinarySearch(TreeNode root, Integer low, Integer up) {
        if (root == null) {
            return true;
        }

        int val = root.val;

        if (low != null && val <= low) {
            return false;
        }
        if (up != null && val >= up) {
            return false;
        }

        if(!isLegalBinarySearch(root.left,low,val)){
            return false;
        }

        if(!isLegalBinarySearch(root.right,val,up)){
            return false;
        }


        return true;
    }


    public static void main(String[] args) {
        t20211019 t20211019 = new t20211019();
        int[][] tesArr = new int[3][3];

        tesArr[0][0] = 2;
        tesArr[0][1] = 1;
        tesArr[0][2] = 1;
        tesArr[1][0] = 1;
        tesArr[1][1] = 1;
        tesArr[1][2] = 0;
        tesArr[2][0] = 0;
        tesArr[2][1] = 1;
        tesArr[2][2] = 1;
        int i = t20211019.orangesRotting(tesArr);
        System.out.println(i);


    }

}
